The World Wide Web (WWW) has evolved from a service focused on academic areas and offering scientific content into a medium for common users to access information of various origins. While surfing the Web, many users are not aware that a large number of organizations such as those in the marketing industry are gathering their private information. This information is supplemented when a user accesses a Web site, clicks a Web page, makes an electronic purchase, or downloads a file. From all the records and computerized analysis, the information collector can build a digital dossier about the users—what they do, where they go, what they read, what they buy, etc.
There has, therefore, been general recognition of the need for privacy protection on the Internet. One situation in which privacy is a large concern is when databases containing users' personal information are accessed. To illustrate, suppose there is a database that maintains groups of digital objects, and a user wishes to retrieve a subset of the digital objects. Two desirable constraints on database access are as follows:                1) the user can access data the user wants, without disclosing to the database the specific digital objects actually desired; and        2) the user can not get any additional information from the database without the consent of the database.The first constraint is referred to as user privacy and the second constraint is referred to as database security.        
One example that illustrates these concepts is the task of providing electronic newspaper services over the Internet. A database maintains a collection of digital news articles. Assuming that a subscriber request n articles, database security requires that the subscriber gets only n articles, while the user privacy requires that the database cannot determine which n specific articles are retrieved by the subscriber.
The problem of private information retrieval was reviewed by B. Chor, O. Goldreich, E. Kushilevaita, and M. Sudan, “Private Information Retrieval,” Proceedings of the 36th Annual Symposium on Foundations of Computer Science, pp, 41–50, 1995. The authors were connected with information-theoretical security and proposed solution using multiple databases. However, the security of this solution relies on the assumption that the multiple databases do not communicate with each other, which is not guaranteed to be the case, and is additionally outside of the user's control and ability to independently verify.
Private information retrieval schemes using a single database were later proposed in B. Chor and N. Gilboa, “Computational Private Information Retrieval,” Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pp. 304–313, 1997, and E. Kushilevita and R. Ostrovsky, “Single-Database Computationally Private Information Retrieval, ” Proceeding of the 38th annual Symposium on Foundation of Computer Science, 1997. These solutions are concerned with security based on computational assumption theory, and in particular the difficulty of factoring large prime numbers, as is done in the well-known RSA encryption scheme. However, the computational costs of these solutions are prohibitively large due to their bit-by-bit processing approach. For example, the scheme in the Kushilevita and Ostrovsky reference requires a computational cost on the order of O(N) multiplication modulo a 1024-bit number just to retrieve 1 bit of information, where N is the number of bits of data maintained by the database.
The requirement of database security in the context of private information retrieval was studied in Y. Gertner, Y. Ishai, E. Kushilevita and T. Malkin, “Protecting Data Privacy in Private Information Retrieval Schemes,” Proceedings of the 30th ACM Annual Symposium on Theory of Computing, 1998.
All of the proposed solutions to the problem of private information retrieval described above employ the bit-by-bit processing approach. Therefore, they have only theoretical values, and are not feasible in practical applications, because of the time that would be required to solve each problem.
Therefore, what is needed is a way of allowing a user to achieve information retrieval from a database in an efficient manner while maintaining privacy.